﻿#include<iostream>
#include<vector>
using namespace std;

//int main()
//{
//    vector<int> v{5};
//    vector<int> vv(5);
//
//    auto it = { 1,2,3,4,5,6,7,8 };
//    for (auto e : it)
//    {
//        cout << e << ' ';
//    }
//    cout << endl;
//    const int&& s = 10;
//    int i = 10;
//    int&& j = move(i);
//    //j = 10;
//    cout << i << j << endl;
//    //s = 20;
//    cout << s << endl;
//    cout << 10 << endl;
//    return 0;
//}

//int add(int x, int y)
//{
//	return x + y;
//}
//
//int add1(int x, int y)
//{
//	int i = x + y;
//	return i;
//}

//vector<int>& a(int x)
//{
//	vector<int> ret;
//	ret.push_back(x);
//
//	return ret;
//}
//
//class Solution {
//public:
//	// 传值返回需要拷⻉
//	string& addStrings(string num1, string num2) {
//		static string str;
//		int end1 = num1.size() - 1, end2 = num2.size() - 1;
//		// 进位
//		int next = 0;
//		while (end1 >= 0 || end2 >= 0)
//		{
//			int val1 = end1 >= 0 ? num1[end1--] - '0' : 0;
//			int val2 = end2 >= 0 ? num2[end2--] - '0' : 0;
//			int ret = val1 + val2 + next;
//			next = ret / 10;
//			ret = ret % 10;
//			str += ('0' + ret);
//		}
//		if (next == 1)
//			str += '1';
//		reverse(str.begin(), str.end());
//		return str;
//	}
//};

//int main()
//{
//	/*double b = 10.111;
//	int* i = move(b);*/
//
//	/*const int& i = move(10);
//	cout << i << endl;*/
//
//	/*cout << add(1, 2) << endl;
//	cout << add1(1, 2) << endl;*/
//
//	//vector<int >ret = a(1);
//	string ret = Solution().addStrings("11111111111111111","222222222222222222222");
//	cout << ret << endl;
//	return 0;
//}

//int main()
//{
//	string s1("xxxxx");
//	// 拷⻉构造
//	string s2 = s1;
//	// 构造+移动构造，优化后直接构造
//	string s3 = string("yyyyy");
//	// 移动构造:就相当于强制抢走了s1中的所有资源，包括地址
//	string s4 = move(s1);
//
//	/*cout << s1 << endl;
//	cout << s2 << endl;
//	cout << s3 << endl;
//	cout << s4 << endl;*/
//	cout << "******************************" << endl;
//	return 0;
//}

//class Solution {
//public:
//	void Qsort(vector<int>& arr, int l, int r, int k)
//	{
//		//升序排序
//		if (l >= r)return;
//		int left = l, right = r, i = l;
//		int key = arr[rand() % (r - l + 1) + l];
//
//		while (i <= r)
//		{
//			if (arr[i] > key)swap(arr[i], arr[right--]);
//			else if (arr[i] == key)i++;
//			else swap(arr[i++], arr[left++]);
//		}
//
//		//[l,left-1][left,right][right+1,r]
//		int a = left - l;
//		int b = right - left + 1;
//		if (a > k) Qsort(arr, l, left - 1, k);
//		else if (a + b >= k) return;
//		else Qsort(arr, right+1, r, k - a - b);
//	}
//
//	vector<int> smallestK(vector<int>& arr, int k) {
//		srand(time(NULL));
//		Qsort(arr, 0, arr.size() - 1, k);
//		return { arr.begin(),arr.begin() + k };
//	}
//};
//class Solution {
//public:
//    void fun(std::vector<int>& nums, int l, int r, int k) {
//        if (l >= r)
//            return;
//
//        int key = nums[rand() % (r - l + 1) + l];
//        int left = l, right = r;
//        int i = l;
//        while (i <= right) {
//            if (nums[i] > key)
//                std::swap(nums[i], nums[right--]);
//            else if (nums[i] < key)
//                std::swap(nums[i++], nums[left++]);
//            else i++;
//        }
//        int a = left - l;
//        int b = right - left + 1;
//        if (a > k)fun(nums, l, left - 1, k);
//        else if (b + a >= k)return;
//        else fun(nums, right + 1, r, k - a - b);
//    }
//
//    vector<int> smallestK(vector<int>& arr, int k) {
//
//        if (arr.size() == k)return arr;
//        srand(time(NULL));
//        fun(arr, 0, arr.size() - 1, k);
//        return { arr.begin(),arr.begin() + k };
//    }
//};
//
//int main()
//{
//	Solution s;
//	vector<int>ss({ 62577, -220, -8737, -22, -6, 59956, 5363, -16699, 0, -10603, 64, -24528, -4818, 96, 5747, 2638, -223, 37663, -390, 35778, -4977, -3834, -56074, 7, -76, 601, -1712, -48874, 31, 3, -9417, -33152, 775, 9396, 60947, -1919, 683, -37092, -524, -8, 1458, 80, -8, 1, 7, -355, 9, 397, -30, -21019, -565, 8762, -4, 531, -211, -23702, 3, 3399, -67, 64542, 39546, 52500, -6263, 4, -16, -1, 861, 5134, 8, 63701, 40202, 43349, -4283, -3, -22721, -6, 42754, -726, 118, 51, 539, 790, -9972, 41752, 0, 31, -23957, -714, -446, 4, -61087, 84, -140, 6, 53, -48496, 9, -15357, 402, 5541, 4, 53936, 6, 3, 37591, 7, 30, -7197, -26607, 202, 140, -4, -7410, 2031, -715, 4, -60981, 365, -23620, -41, 4, -2482, -59, 5, -911, 52, 50068, 38, 61, 664, 0, -868, 8681, -8, 8, 29, 412});
//	cout<<ss.size();
//	s.smallestK(ss,131);
//	return 0;
//}


//归并排序,递归实现
void mergeSort(vector<int>&nums,vector<int>&tem,int left,int right)
{
	if (left >= right)return;

	//找到中间值
	int mid = (left + right) >> 1;

	//分治
	mergeSort(nums, tem, left, mid);
	mergeSort(nums, tem, mid+1,right);

	//开始合并两个区间
	int cur1 = left, cur2 = mid + 1;
	int i = left;
	while (cur1 <= mid && cur2 <= right)
		tem[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
	while (cur1 <= mid)tem[i++] = nums[cur1++];
	while (cur2 <= right)tem[i++] = nums[cur2++];

	////最后合并
	for (int i = left; i <= right; i++)
		nums[i] = tem[i];

}

#include<list>

int main()
{
	vector<int>nums({ 9,8,7,6,5,4,3,2,1 });
	vector<int>tem(nums.size());
	for (auto e : nums)cout << e << ' ';

	mergeSort(nums, tem, 0, nums.size() - 1);
	cout << endl;
	for (auto e : nums)cout << e << ' ';


	list<int>st;
	st.insert(st.begin(), 1);
	st.insert(st.begin(), 2);
	st.insert(st.begin(), 3);
	st.insert(st.begin(), 4);



	return 0;
}
